package 剑指offer.链表中倒数第k个节点_14;

import java.util.Stack;

public class Main {
    public ListNode FindKthToTail(ListNode head,int k) {
    	if(head == null) return null;
    	Stack<ListNode> stack = new Stack<ListNode>();
    	while(head != null){
    		stack.push(head);
    		head = head.next;
    	}
    	for(int i = 0; i < k; i++){
    		if(stack.empty()) return null;
    		head = stack.pop();
    	}
    	return head;
    }
    
    public ListNode FindKthToTail2(ListNode head,int k) {
    	if(head == null) return null;
    	ListNode head1 = head;
    	int num = 0;
    	while(head != null){
    		num++;
    		head = head.next;
    	}
    	if(k > num) return null;
    	for(int i = 0; i < num-k; i++){
    		head1 = head1.next;
    	}
    	return head1;
    }
    
    public ListNode FindKthToTail3(ListNode head,int k) {
    	if(head == null) return null;
    	ListNode pre = null, p = null;
    	p = head;
    	pre = head;
    	int a = k;
    	int count = 0;
    	while(p != null){
    		p = p.next;
    		count++;
    		if(k < 1){
    			pre = pre.next;
    		}
    		k--;
    	}
    	if(count < a) return null;
    	return pre;
    }
}
